#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;

class Solution{
    public:
    //双指针
    double ans1(vector<int>& nums1, vector<int>& nums2){
        int m = nums1.size(), n = nums2.size();
        int len = m + n;
        int p1 = 0, p2 = 0;
        int flag;
        if(len % 2 == 0){
            flag = 0;
        }else{
            flag = 1;
        }
        
        queue<int> temp;
        temp.push(0);
        temp.push(0);

        for(int i = 0; i != len/2+1; i++){
            if(nums1[p1] <= nums2[p2] && p1 < m){
                temp.pop();
                temp.push(nums1[p1]);
                p1++;
            }else if(nums1[p1] > nums2[p2] && p2 < n){
                temp.pop();
                temp.push(nums2[p2]);
                p2++;
            }else if(p1 == m){
                temp.pop();
                temp.push(nums2[p2]);
                p2++;
            }else if(p2 == n){
                temp.pop();
                temp.push(nums1[p1]);
                p1++;
            }
        }

        double ret;   
        if(flag == 0){
            ret = (temp.back() + temp.front()) / 2.0;
        }else{
            ret = temp.back();
        }

        return ret;
    }

    //合并数组
    double ans2(vector<int>& nums1, vector<int>& nums2){
        nums1.insert(nums1.end(), nums2.begin(), nums2.end());
        sort(nums1.begin(), nums1.end());
        int len = nums1.size();
        double ret;
        if(len % 2 == 0){
            ret = (nums1[len/2] + nums1[len/2-1]) / 2.0;
        }else{
            ret = nums1[len/2];
        }

        return ret;
    }
};

void test1(){
    Solution s;
    vector<int> nums1 = {1,3};
    vector<int> nums2 = {2};

    double ret = s.ans1(nums1, nums2);
    cout << ret << endl;
}

void test2(){
    Solution s;
    vector<int> nums1 = {1,2};
    vector<int> nums2 = {3,4};

    double ret = s.ans1(nums1, nums2);
    cout << ret << endl;
}

int main(void){
    test1();
    test2();

    return 0;
}